package org.shj.suanfa

//8皇后问题：

object EightQueen {
  def main(args: Array[String]): Unit = {
    queens(4).foreach(println)
  }
  
  def queens(n: Int): List[List[(Int, Int)]] = {
    def placeQueens(k: Int): List[List[(Int, Int)]] = {
      //println(s"placeQueens($k)")
      
      if(k == 0)
        List(List())
      else
        for{
          queens <- placeQueens(k-1)
          column <- 1 to n
          queen= (k, column)
          if isSafe(queen, queens)
        }yield queen :: queens
      
    }
    
    placeQueens(n)
  }
  
  def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) ={
    //queens.foreach(print(_))
    //println(", queen:" + queen)
    queens.forall(q => !inCheck(queen,q))
  }
  
  def inCheck(q1: (Int,Int), q2:(Int,Int)) = {
    q1._1 == q2._1 ||                           //同行
    q1._2 == q2._2 ||                           //同列
    (q1._1 - q2._1).abs == (q1._2 - q2._2).abs  //对角线
  }
}